還記得之前有討論過的列舉法嗎？今天我們來做個延伸。

之前的列舉法是將用 for 迴圈的方式，一層一層的舉出所有的可能，然後將所有舉出的可能和我們所設定的條件相比對，若符合則輸出。但這邊問題來了，題目設定的是 0 到 9 的數字，那若將題目加以變更從 1 到 100，甚至 1 到 1000呢？那 for 迴圈不就要寫千百次？那是不可能的。所以有了遞迴的方法。

深度搜尋 (Depth-first Search)，其實就是遞迴的一種運用沒錯，一層一層地找出所有可能，但程式碼卻會簡潔的多。

直接舉個例子吧。之前用列舉法所要找的數字排列，以符合方程式。

[1, 2, 3, 4, 5, 6, 7, 8, 9]

將數字 1 到 9 填入上面的方程式，使之為 1 。

接下來我們會用兩個陣列，一個是用來放數字並嘗試運算解的陣列，另一個是用來標示數字是否被取用的陣列。

深度優先搜尋法

a = [] 
book = []
for i in range(10):
    a.append(0)     #設數字9+1個空盒子
    book.append(0)  #設數字9+1個空盒子，表示目前是否有使用此數字

total = 0 #代表可行解總共有幾種
def dfs(step, total, a, book):  #step代表目前的位置
    if step == 9:   #如果站在索引為9的盒子表示0~8共九個位置都已有待運算的數字
        if a[0]/(a[1]*10.+a[2]) + a[3]/(a[4]*10.+a[5]) + a[6]/(a[7]*10.+a[8]) == 1 : 
            total += 1  #如果滿足解，可行解+1
            print(a)
        return total    #返回之前的一步(最接近呼叫的地方)
    
    #站在地step位置，按照0~8的順序一一的嘗試
    for i in range(9):
        if book[i] == 0 :  #如果book[i]等於0，代表這個位置的數字可以用
            a[step] = i+1  #將可用數字給到空盒子裡(因為i為索引，所以要加1)
            book[i] = 1    #表示這個位置的數字已被取用

            total = dfs(step + 1, total, a, book) #藉由遞迴來找出更深層的解

            book[i] = 0    #但記得要把剛才嘗試過的數字重置，才能進行下一次的嘗試
    return total


total = dfs(0, total, a, book)
print(total/2)  #因為有重複解，所以要除以2

列舉法

from copy import copy
list_1to9=[1,2,3,4,5,6,7,8,9]

#在b層建一個新的1-9，然後pop掉取過的，C層再複製b取過的，建一個新的1-9，pop調取過的
#d層再複製c層取過的，建新的1-9.....以下同上。這樣就最後一行就不用再把取過的加回去了。

# 如果再稍稍修改，效率會再更好喔
for a in list_1_to_9:        # a從list_1to9取數字
	list_a=copy(list_1to9)   # list_a複製list_1to9
	list_a.remove(a)         # 將a選取的數字從list_a去除，留下可以繼續被選取的字給b
	for b in list_a:         # b從list_a取數字
		list_b=copy(list_a)  # list_b複製list_a
		list_b.remove(b)     # 將b選取的數字從list_b去除，留下可以繼續被選取的字給c
		for c in list_b:
			list_c=copy(list_b)
			list_c.remove(c)
			for d in list_c:
				list_d=copy(list_c)
				list_d.remove(d)
				for e in list_d:
					list_e=copy(list_d)
					list_e.remove(e)
					for f in list_e:
						list_f=copy(list_e)
						list_f.remove(f)
						for g in list_f:
							list_g=copy(list_f)
							list_g.remove(g)
							for h in list_g:
								list_h=copy(list_g)
								list_h.remove(h)
								for i in list_h:
                                    #這時候選取完所有的數字，並填入方程式進行驗證，如果為是，輸出結果；如果為否，則沿著迴圈h到迴圈a一一測試各種可能。
									if (a/(b*10.+c)+d/(e*10.+f)+g/(h*10.+i))==1: 
										print (a,b,c,d,e,f,g,h,i) 

可以比較看看兩者的差別。